package cg.studio.practise;

import cg.studio.algorithm.collection.Collections;

/**
 * This class solve the problem of integer combination with same sum
 * for example, sum is 4, the combination are Combination(4): 1,1,1,1; 1,1,2; 1,3; 2,2; 4
 * 
 * this class solve this problem by following idea:
 * assume the max value one combination is m ( m<sum ); then this combination could be m, combination( sum -m, m )
 * Combination ( n, m ) mean the combination which sum is n, max value is m 
 * Combination( n, m ) == Combination ( n ) if m >= n 
 * 
 * for previous example:
 * C(4) => C(4, 4)
 * 1, C(3, 1) => 1, C(3,1) => 1, 1, 1, 1
 * 2, C(2, 2) => 2, C(2) => 2, { 1,  1 }
 * 3, C(1, 3) => 3, C(1) => 3, 1
 * 4, C(0, 4) => 4
 * 
 * @author Bright Chen
 *
 */
public class SumSequence
{
  private static final int SIZE = 5;


  public static void main( String[] argvs )
  {
    printSeq( SIZE );
  }

  public static void printSeq( int size )
  {
    SumSequence ss = new SumSequence( size );
    ss.printSeq( size, 0, 1 );
  }

  protected int[] arr;
  
  protected SumSequence( int size )
  {
    arr = new int[size];
  }
  
  /**
   * 
   * @param remainSum the sum of this integer sequences.
   * @param fixedLen how many numbers had already fixed, in fact, the start index of remain sequence
   * @param startValue the value going to be put to as fixing number
   */
  protected void printSeq( int remainSum, int fixedLen, int startValue )
  {
    if ( remainSum <= 0 )
    {
      Collections.printArray( arr, 0, fixedLen );
      System.out.println();
      return;
    }

    /*************
    for ( int value = startValue; value <= fixingNum; value++ )
    {
      arr[fixedLen] = value;
      printSeq( fixingNum - value, fixedLen + 1, value );
    }
    /*************/
    
    for ( int value = startValue; value <= remainSum; value++ )
    {
      arr[fixedLen] = value;
      printSeq( remainSum - value, fixedLen + 1, value );
    }

  }
  
}
